/*
https://leetcode.cn/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/solution/cdong-tai-gui-hua-bi-sai-de-shi-hou-bei-fan-yi-ken/
 */
public class Solution1467 {
    public double getProbability(int[] balls) {
        double[][][] f=new double[balls.length+1][50][balls.length*2+1];
        f[0][0][balls.length]=1;
        int sum=0;
        for (int i=1;i<=balls.length;i++){
            sum+=balls[i-1];
            for (int j=0;j<=sum;j++){
                for (int k=0;k<=balls.length*2;k++){
                    for (int r=0;r<=balls[i-1] && j>=r;r++){
                        if (r==0 && k>0){
                            f[i][j][k]+=f[i-1][j-r][k-1]*c(j,r)*c(sum-j,sum-j-(balls[i-1]-r));
                        }
                        if (r==balls[i-1] && k<balls.length*2){
                            f[i][j][k]+=f[i-1][j-r][k+1]*c(j,r)*c(sum-j,sum-j-(balls[i-1]-r));
                        }
                        if (r>0 && r<balls[i-1]){
                            f[i][j][k]+=f[i-1][j-r][k]*c(j,r)*c(sum-j,sum-j-(balls[i-1]-r));
                        }
                    }
                }
            }
        }
        double total=1;
        total*=f(sum);
        for (int ball : balls) {
            total/=f(ball);
        }
        return f[balls.length][sum/2][balls.length]/total;
    }

    private double c(int i, int j) {
        return 1.0*f(i)/f(j)/f(i-j);
    }

    private double f(int i) {
        double t=1;
        for (int k=1;k<=i;k++){
            t*=k;
        }
        return t;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1467().getProbability(new int[]{6,6,6,6,6,6}));
    }
}
